/* 
 * File:   SimpleGraph.cpp
 * Author: RaF
 * 
 * Created on 22 novembre 2012, 17.12
 */
#include <stddef.h>


#ifndef SIMPLEGRAPH_H
#define	SIMPLEGRAPH_H

#include <vector>
#include <list>
#include <map>
#include "Edge.hpp"
#include "Vertex.hpp"
#include "Graph.h"
#include "VertexSet.hpp"
#include "QuickSort.hpp"
#include "VisitInfo.hpp"

template <typename I> class SimpleGraph : public Graph<I> {
public:
    SimpleGraph();
    SimpleGraph(const SimpleGraph& orig);
    virtual ~SimpleGraph();

    //Metodi iteratore

    std::vector<Vertex<I>*>* getVertices() {
        return vertices;
    }
    std::vector<Edge<I>*>* getEdges();

    std::list<Edge<I>*>* getAdjacentsEdges(Vertex<I>* v) {
        return v->getAdjacencyList();
    }

    //Metodi di accesso
    std::vector<Vertex<I>*>* getEndVertices(Edge<I>* e);
    Vertex<I>* getOpposite(Vertex<I>* v, Edge<I>* e);
    bool areAdjacent(Vertex<I>* v, Vertex<I>* w);
    void insertVertex(I info);
    virtual void insertEdge(Vertex<I>* v, Vertex<I>* w, int edgeWeight);
    virtual void removeVertex(Vertex<I>* v);
    virtual void removeEdge(Edge<I>* e);
    //visita di profondità del grafo 
    std::map<Vertex<I>*, Vertex<I>*>* VisitByDFS(void (*doAction)(Vertex<I>* v));
    //Ricerca dell'albero di copertura minimo
    std::vector<Edge<I>*>* kruskal();

protected:
    //vettore in cui l'i-esimo elemento contiene sia un vertice,
    //che la lista di tutti i vertici adiacenti
    std::vector<Vertex<I>*>* vertices;
    int nextFreeLabel;
    //restituisce l'indice relativo al vettore "vertices", -1 altrimenti
    int searchVertex(int label);
    //ottiene riferimento al vertice trovato nella lista
    Vertex<I>* searchVertexFromAdjacenceEdgeList(std::list<Edge<I>*>* list, int label);
    //funzione da richiamare ricorsivamente dalla funzione di visita in profondità
    void DFSVisit(int vertexLabel, int* time, std::map<int, VisitInfo> *visitInfo, std::map<Vertex<I>*, Vertex<I>* > *parentMap, void (*doAction)(Vertex<I>* v));



};

template <typename I> SimpleGraph<I>::SimpleGraph() {
    this->vertices = new std::vector<Vertex<I>*>();
    this->nextFreeLabel = 0;

}

template <typename I> SimpleGraph<I>::SimpleGraph(const SimpleGraph& orig) {
    this->vertices = new std::vector<Vertex<I>*>(orig.vertices->size());
    for (int i = 0; i < orig.vertices->size(); i++)
        this->vertices.at(i) = orig.vertices.at(i);
}

template <typename I> SimpleGraph<I>::~SimpleGraph() {
    for (int i = 0; i < this->vertices->size(); i++)
        delete this->vertices->at(i);
    delete this->vertices;
}

template <typename I> std::vector<Edge<I>*>* SimpleGraph<I>::getEdges() {
    std::vector<Edge<I>*>* edges = new std::vector<Edge<I>*>();
    std::list<Edge<I>*>* list;
    for (int i = 0; i<this->vertices->size(); i++) {
        list = vertices->at(i)->getAdjacencyList();
        if (!list->empty()) {
            typename std::list<Edge<I>*>::const_iterator it;
            for (it = list->begin(); it != list->end(); ++it) {
                //inserisco nel vettore di archi (inserisco sia (u,v) che (v,u))
                edges->push_back(*it);
            }
        }
    }

    return edges;
}


//Metodi di accesso

/**
 * Ottiene i vertici connessi dall'arco specificato
 * @param e arco che unisce i due vertici
 * @return vertici connessi dall'arco
 */
template <typename I> std::vector<Vertex<I>*>* SimpleGraph<I>::getEndVertices(Edge<I>* e) {
    std::vector<Vertex<I>*>* endVertices = new std::vector<Vertex<I>*>(2);
    endVertices->push_back(e->getFrom());
    endVertices->push_back(e->getTo());
    return endVertices;
}

template <typename I> Vertex<I>* SimpleGraph<I>::getOpposite(Vertex<I>* v, Edge<I>* e) {
    if (e->getFrom()->getLabel() == v->getLabel())
        return e->getTo();
    else if (e->getTo()->getLabel() == v->getLabel())
        return e->getFrom();
    else
        //caso in cui il vertice passato come parametro non è connesso all'arco specificato
        return NULL;
}

template <typename I> bool SimpleGraph<I>::areAdjacent(Vertex<I>* v, Vertex<I>* w) {
    int labelToCompare;

    std::list<Edge<I>*>* list;
    if (v->getAdjacencyList()->size() > w->getAdjacencyList()->size()) {
        list = w->getAdjacencyList();
        labelToCompare = v->getLabel();
    } else {
        list = v->getAdjacencyList();
        labelToCompare = w->getLabel();
    }

    return (searchVertexFromAdjacenceEdgeList(list, labelToCompare) != NULL);

}

template <typename I> void SimpleGraph<I>::insertVertex(I info) {
    Vertex<I>* v = new Vertex<I > (this->nextFreeLabel++, info);
    this->vertices->push_back(v);
}


///PRECONDIZIONE: l'arco da inserire non è già presente nel grafo

template <typename I> void SimpleGraph<I>::insertEdge(Vertex<I>* v, Vertex<I>* w, int edgeWeight) {
    //essendo un grafo semplice, inserisco l'arco sia nella lista di adiacenza di v che di w
    Edge<I>* fromVtoW = new Edge<I > (v, w, edgeWeight);
    Edge<I>* fromWtoV = new Edge<I > (w, v, edgeWeight);
    v->getAdjacencyList()->push_back(fromVtoW);
    w->getAdjacencyList()->push_back(fromWtoV);
}

template <typename I> void SimpleGraph<I>::removeVertex(Vertex<I>* v) {
    int labelToRemove = v->getLabel();
    //cerco nodo da eliminare
    int index = searchVertex(labelToRemove);

    if (index>-1) {
        //salvo i vertici che erano connessi a questo, per poi andare ad
        //eliminare gli archi connessi a v nelle liste di adiacenza degli altri vertici
        std::vector<Vertex<I>*>* connectedVertices = new std::vector<Vertex<I>*>();
        typename std::list<Edge<I>*>::iterator it;
        std::list<Edge<I>*>* list = vertices->at(index)->getAdjacencyList();
        for (it = list->begin(); it != list->end(); ++it) {
            connectedVertices->push_back((*it)->getTo());
        }

        //elimino i riferimenti alle adiacenze dalle liste
        for (int i = 0; i < connectedVertices->size(); i++) {
            bool deleted = false;
            Vertex<I>* w = connectedVertices->at(i);
            //cerco il vertice dalla cui lista eliminare l'arco al nodo v già eliminato.
            int wIndex = searchVertex(w->getLabel());
            std::list<Edge<I>*>* list = vertices->at(wIndex)->getAdjacencyList();
            typename std::list<Edge<I>*>::iterator it = list->begin();

            while (!deleted && it != list->end()) {
                if ((*it)->getTo()->getLabel() == labelToRemove) {
                    list->erase(it);
                    deleted = true;
                }
                ++it;
            }
        }

        //elimino l'elemento dal vettore e la sua lista di adiacenza
        typename std::vector<Vertex<I>*>::iterator verticesIt = this->vertices->begin();
        std::advance(verticesIt, index);
        this->vertices->erase(verticesIt);

        delete connectedVertices;
    }
}

template <typename I> void SimpleGraph<I>::removeEdge(Edge<I>* e) {
    //elimino sia l'arco (u,v) che l'arco (v,u)
    int index = searchVertex(e->getFrom()->getLabel());
    std::list<Edge<I>*>* list = vertices->at(index)->getAdjacencyList();
    bool deleted = false;
    typename std::list<Edge<I>*>::iterator it = list->begin();
    while (!deleted && it != list->end()) {
        if ((*it)->getTo()->getLabel() == e->getTo()->getLabel()) {
            list->erase(it);
            deleted = true;
        }
        ++it;
    }

    index = searchVertex(e->getTo()->getLabel());
    list = vertices->at(index)->getAdjacencyList();
    it = list->begin();
    deleted = false;
    while (!deleted && it != list->end()) {
        if ((*it)->getTo()->getLabel() == e->getFrom()->getLabel()) {
            list->erase(it);
            deleted = true;
        }
        ++it;
    }
}

template <typename I> int SimpleGraph<I>::searchVertex(int label) {
    int index = 0;
    bool found = false;
    //cerco il nodo da eliminare
    while (index < this->vertices->size() && !found) {
        if (this->vertices->at(index)->getLabel() == label) {
            found = true;
        } else
            index++;
    }
    if (!found)
        return -1;
    else
        return index;
}

template <typename I> Vertex<I>* SimpleGraph<I>::searchVertexFromAdjacenceEdgeList(std::list<Edge<I>*>* list, int label) {
    bool found = false;
    typename std::list<Edge<I>*>::iterator it = list->begin();

    //cerco il nodo da eliminare
    //la cerco in to
    while (it != list->end() && !found) {
        if ((*it)->getTo()->getLabel() == label) {
            found = true;
        } else
            ++it;
    }
    if (!found)
        return NULL;
    else
        return (*it)->getTo();
}
/**
 * Ottiene il Minimum Spanning Tree(MST) del grafo
 * @return un vettore di riferimenti ad archi costituenti il MST
 */
template <typename I> std::vector<Edge<I>*>* SimpleGraph<I>::kruskal() {
    //Inizializzo il vettore che conterrà l'albero di copertura minimo
    std::vector<Edge<I>*>* mst = new std::vector<Edge<I>*>();
    //Inizializzo la struttura che conterrà gli insime di sotto-grafi connessi
    VertexSet set;
    //Creo un insieme per ogni vertice presente
    typename std::vector<Vertex<I>*>::iterator vertexIt;
    for (vertexIt = this->vertices->begin(); vertexIt != this->vertices->end(); ++vertexIt) {
        set.makeSet((*vertexIt)->getLabel());
    }

    //Ordino archi in senso non decrescente rispetto al peso
    std::vector<Edge<I>*>* edges = getEdges();
    QuickSort<Edge<I>*> *s = new QuickSort<Edge<I>*>();
    s->sortVector(edges);
    delete s;
    
    typename std::vector<Edge<I>*>::iterator edgeIt;
    //Ad ogni iterazione scelgo l'arco a peso minimo che sia sicuro rispetto
    // al sotto-albero di connessione minima fin ora calcolato
    for (edgeIt = edges->begin(); edgeIt != edges->end(); ++edgeIt) {
        //Controllo se l'arco unisce due componenti connesse diverse
        if (set.find((*edgeIt)->getFrom()->getLabel()) != set.find((*edgeIt)->getTo()->getLabel())) {
            //Inserisco l'arco nel sotto-albero a connessione minima
            mst->push_back(*edgeIt);
            //Unisco le due componenti connesse 
            set.unionSet(set.find((*edgeIt)->getFrom()->getLabel()), set.find((*edgeIt)->getTo()->getLabel()));
        }
    }

    delete edges;
    return mst;
}

/**
 * Esegue la visita di profondità del grafo
 * @param doAction procedura che verrà eseguita su ogni vertice del grafo
 * @return mappa chiave/valore delle relazioni di parentela negli alberi dei vertici visitati.
 * La chiave corrisponde al vertice figlio, mentre il valore al vertice padre.
 */
template <typename I> std::map<Vertex<I>*, Vertex<I>*>* SimpleGraph<I>::VisitByDFS(void (*doAction)(Vertex<I>* v)) {

    VertexColor color;
    std::map<int, VisitInfo> verticesInfo;
    int verticesSize = this->vertices->size();
    //mappa contentente le relazioni di parentela negli alberi dei vertici visitati. Chiave:vertice figlio, Valore: vertice padre.
    std::map<Vertex<I>*, Vertex<I>*>* parentMap = new std::map<Vertex<I>*, Vertex<I>*>();
    //fase di inizializzazione
    //inizializzo la variabile temporale
    int time = 0;
    //inizializzo le informazioni per la visita
    color = WHITE;
    VisitInfo info(color, time);
    int label;
    for (int i = 0; i < verticesSize; i++) {
        label = this->vertices->at(i)->getLabel();
        verticesInfo.insert(std::pair<int, VisitInfo > (label, info));
        //imposto il padre dell'i-esimo vertice a NULL
        parentMap->insert(std::pair<Vertex<I>*, Vertex<I>*>(this->vertices->at(i), NULL));
    }
    //richiamo la DFSVisit sui sottografi ancora inesplorati
    for (int i = 0; i < verticesSize; i++) {
        label = vertices->at(i)->getLabel();
        //se color[u]==WHITE
        if (verticesInfo.at(label).getColor() == WHITE)
            DFSVisit(label, &time, &verticesInfo, parentMap, doAction);
    }
    return parentMap;
}

/**
 * Metodo privato utilizzato dalla VisitByDFS. Esegue la visita ricorsivamente
 * su tutti i vertici adiacenti al vertice considerato.
 * @param vertexLabel label del vertice considerato
 * @param time riferimento al tempo di visita
 * @param visitInfo informazioni necessarie alla visita dei vertici del grafo
 * @param parentMap mappa chiave valore delle relazioni di parentela negli alberi dei vertici visitati.La chiave corrisponde al vertice
 * figlio, mentre il valore al vertice padre.
 * @param doAction procedura che verrà eseguita su ogni vertice del grafo
 */
template <typename I> void SimpleGraph<I>::DFSVisit(int vertexLabel, int* time, std::map<int, VisitInfo> *visitInfo, std::map<Vertex<I>*, Vertex<I>* > *parentMap, void (*doAction)(Vertex<I>* v)) {
    //color[u]=Grey
    (visitInfo->at(vertexLabel)).setColor(GREY);
    *time = *time + 1;
    visitInfo->at(vertexLabel).setStartTime(*time);
    int index = searchVertex(vertexLabel);
    Vertex<I>* u = this->vertices->at(index);
    //esegue l'azione specificata dall'utente su ogni vertice
    if(doAction!=NULL)
        doAction(u);
    //ottengo la lista dei vertici adiacenti al vertice considerato
    std::list<Edge<I>*>* list = u->getAdjacencyList();
    typename std::list<Edge<I>*>::iterator it;
    //per tutti i nodi adiacenti al vertice considerato (di label "vertexLabel")
    Vertex<I>* v;
    VertexColor adjColor;
    for (it = list->begin(); it != list->end(); ++it) {
        v = (*it)->getTo();
        adjColor = visitInfo->at(v->getLabel()).getColor();
        //if color[v]==WHITE
        if (adjColor == WHITE) {
            //pi[v]=u;
            parentMap->at(v) = u;
            //richiamo ricorsivamente la DFSVisit sui vertici adiacenti
            DFSVisit(v->getLabel(), time, visitInfo, parentMap, doAction);

        }
    }
    //setto il colore(nero) e l'endTime del vertice considerato
    visitInfo->at(vertexLabel).setColor(BLACK);
    *time = *time + 1;
    visitInfo->at(vertexLabel).setEndTime(*time);
}


#endif	/* SIMPLEGRAPH_H */
